MIME-Version: 1.0
Server: CERN/3.0
Date: Sunday, 24-Nov-96 22:37:29 GMT
Content-Type: text/html
Content-Length: 5209
Last-Modified: Friday, 15-Nov-96 18:50:35 GMT

<HTML>

<HEAD>
<TITLE>CS381/481 Fall 96 Course Information</TITLE>
</HEAD>

<BODY>

<H1>
CS381/481 Fall 1996<br>
Automata and Computability Theory<br>
Course Information
</H1>

<HR>

<H2>Table of Contents</H2>

<UL>
<LI><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><A HREF="#1">Personnel</A>
<LI><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><A HREF="#2">Time and Place</A>
<LI><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><A HREF="#3">Office Hours</A>
<LI><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><A HREF="#4">Sources</A>
<LI><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><A HREF="#5">Homework and Exams</A>
<LI><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><A HREF="#6">CS381 vs. CS481</A>
</UL>

<hr>

<H2><A NAME = "1">Personnel</a></H2>
<H3>Instructors</H3>
<!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><img align=top src="http://www.cs.cornell.edu/Info/People/pearson/pearson-thumb.gif"><br>
381: <!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><A href="http://www.cs.cornell.edu/home/pearson/pearson.html">David Pearson</a><br>
<!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><a href="mailto:pearson@cs.cornell.edu"><kbd>pearson@cs.cornell.edu</kbd></a><br>
Upson 5133<br>
255-9189

<p>

<!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><img align=top src="http://www.cs.cornell.edu/Info/People/kozen/kozen-thumb.gif"><br>
481: <!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><A href="http://www.cs.cornell.edu/Info/People/kozen/kozen.html">Dexter Kozen</a><br>
<!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><a href="mailto:kozen@cs.cornell.edu"><kbd>kozen@cs.cornell.edu</kbd></a><br>
Upson 5143<br>
255-9209

<hr>

<H3>Teaching Assistants</H3>
<!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><img align=top src="http://www.cs.cornell.edu/Info/People/fcc/fcc-thumb.gif"><br>
381: <!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><A href="http://www.cs.cornell.edu/Info/People/fcc/fcc.html">Francis Chu</a><br>
<!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><a href="mailto:fcc@cs.cornell.edu"><kbd>fcc@cs.cornell.edu</kbd></a><br>
5153 Upson <br>
255-1237

<p>

<!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><img align=top src="http://www.cs.cornell.edu/Info/Courses/Current/CS481/mateev-thumb.gif"><br>
481: <!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><A href="http://www.cs.cornell.edu/home/mateev/mateev.html">Nikolay Mateev</a><br>
<!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><a href="mailto:mateev@cs.cornell.edu"><kbd>mateev@cs.cornell.edu</kbd></a><br>
4156 Upson<br>
255-5033

<hr>

<H2><A NAME = "2">Time and Place</A></H2>
<UL>
<LI>381: MWF 9:05-9:55 Olin 245
<LI>481: MWF 9:05-9:55 Snee 1120 
</UL>

<hr>

<H2><A NAME = "3">Office Hours</A></H2>
<UL>
<LI> Kozen: Upson 5143, TTh 10-11:30am 
<LI> Pearson: Upson 5133, MWF 10-11am
<LI> Chu: Upson 5153, TuTh 2:30-4:00pm
<LI> Mateev: Upson 343B, MWF 2:30-3:30pm
</UL>

<hr>

<H2><A NAME = "4">Sources</A></H2>

<H3>Texts</H3>

There is no required text.  The entire course is covered by the
lecture notes, which are accessible online from the course home page.
The notes are also available in hardcopy for $7 from Linda Mardel,
5147 Upson.

You may also find the following supplementary texts useful.  They are
on reserve in the Engineering Library, Carpenter Hall.

<UL>
<li> J. E. Hopcroft and J. D. Ullman. <i>Introduction to Automata
Theory, Languages, and Computation</i>.  Addison-Wesley, 1979.
<LI> H. Lewis and C. Papadimitriou. <i>Elements of the Theory of
Computation</i>.  Prentice-Hall, 1981.
<LI> M. A. Harrison. <i>Introduction to Formal Language Theory</i>.
Addison-Wesley, 1978.
<LI> N. J. Cutland. <i>Computability</i>. Cambridge Univ. Press, 1980.
</UL>

<H3>Handouts</H3>

All handouts, homework sets, etc. will be available online.  They are
accessible from the course home page.  Most of the notes are in
postscript format, so you will need access to a postscript previewer
such as "ghostview" or postscript printer.  All the printers in the
undergraduate labs handle postscript.  Please contact us if you
experience difficulties.

<p> Homework sets and handouts will be posted periodically.  It is
your responsibility to check for new postings.  New postings will be
announced in the newsgroup <kbd>cornell.class.cs481</kbd>.

<H3>Public Newsgroup</H3>

A public newsgroup <kbd>cornell.class.cs481</kbd> has been created for
technical discussions, questions, and announcements concerning 381 and
481.  Please feel free to use this group as you would any newsgroup or
bulletin board.  Free-ranging technical discussions are especially
encouraged.  We will try to respond to questions posted to this group
within one working day.

<hr>

<H2><A NAME = "5">Homework and Exams</A></H2>

There will be weekly homework assignments consisting of 4-6 problems,
due Wednesday at 4pm.  You can pass it in in class on Wednesday
morning, or get it to the appropriate TA before 4pm without penalty.
You must pass it in to the TA, not to the instructor, secretary, or
undergrad office.  Slip it under his door if he's not there; he'll
collect them shortly after 4pm.  No late homework will be accepted
without a good excuse.  Please clear it with the TA in advance if
possible.  We will have the homework graded and back to you by Friday.
Homework must be submitted in hardcopy form; no email, please.
Homework assignments and solutions will be available online and
accessible from the course home page.

<p> There will be two 50-minute prelim exams and one 100 minute
(cumulative) final exam.  Exams are open book and notes.

<p> The prelims, final and homework will each be worth approximately a
third of your grade.

<hr>

<H2><A NAME = "6">CS381 vs. CS481</A></H2>

CS381 and CS481 follow roughly the same syllabus, but 481 is
faster-paced and goes into more depth.  It is meant for more
theoretically inclined students, grad students, and undergrads bound
for grad school.  Corrective shifting is encouraged in the first few
weeks.  If you are not sure which course is right for you, please come
talk to us.

<hr>
<!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><img align=top src="http://www.cs.cornell.edu/Info/Misc/images/hand_point1.gif">
<!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><a href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/CS481.html">CS381/481 home page</a>
